題目

給一個型別為string的boolean expression，回傳結果(true or false)
experssion包含

1. "t" = true
2. "f" = false
3. "!(expr)", where expr = "f" or "t"
4. &(expr1,expr2,...), where expr = "f" or "t"
5. |(expr1,expr2,...), where expr = "f" or "t"

• Example
  • &(t,f), return false
  • |(&(t,f,t),!(t)), return false

解法

• 類似做加減乘除運算表示的解法，平常看到是中序表示法，會轉成前敘或後敘去解。

• 那這裡我們可以看到題目的三種運算 ｜,＆,！，後面一定有 ()，

• 所以我們能右往左丟進stack，當遇到3個運算符，再將前面丟的拿出來做掉，直到遇到 )。

• 逗號部分不影響，所以直接忽略即可!。

• 基本上分不同運算去處理，就完成了

Code

class Solution {
public:
    bool parseBoolExpr(string s) {
        stack<char> stack;
        
        for(int i = s.length() - 1; i >= 0; i--){
            if(s[i] == '|'){
                bool result = false;
                while(stack.size()){
                    if(stack.top()=='('){
                        stack.pop();
                    }
                    else if(stack.top()=='t'){
                        result|=1;
                        stack.pop();
                    }
                    else if(stack.top()=='f'){
                        result|=0;
                        stack.pop();
                    }
                    else if(stack.top()==')'){
                        stack.pop();
                        stack.push(result==true?'t':'f');
                        break;
                    }
                }
            }
            else if(s[i]=='!'){
                bool result=false;
                while(stack.size()){
                    if(stack.top()=='('){
                        stack.pop();
                    }
                    else if(stack.top()=='t'){
                        result|=1;
                        stack.pop();
                    }
                    else if(stack.top()=='f'){
                        result|=0;
                        stack.pop();
                    }
                    else if(stack.top()==')'){
                        stack.pop();
                        stack.push(!result==true?'t':'f');
                        break;
                    }
                }
               
            }
            else if(s[i]=='&'){
                bool result=true;
                while(stack.size()){
                    if(stack.top()=='('){
                        stack.pop();
                    }
                    else if(stack.top()=='t'){
                        result&=1;
                        stack.pop();
                    }
                    else if(stack.top()=='f'){
                        result&=0;
                        stack.pop();
                    }
                    else if(stack.top()==')'){
                        stack.pop();
                        stack.push(result==true?'t':'f');
                        break;
                    }
                }
            }
            else if(s[i]==','){
                continue;
            }
            else{
                stack.push(s[i]);
            }
        }
        if(stack.size()){
            if(stack.top()=='t'){
                return true;
            }
            else{
                return false;
            }
        }
        return true;
    }
};